
// 方案二：原地更新
// 时间复杂度：O(mn)
// 空间复杂度：O(1)
void gameOfLife(int** board, int boardSize, int* boardColSize) {
    int directions[8][2] = {
        {-1, 0}, {1, 0}, {0, -1}, {0, 1},
        {-1, -1}, {-1, 1}, {1, -1}, {1, 1}
    };
    int m = boardSize;
    int n = *boardColSize;

    // 遍历每个细胞，并确定它最终的状态
    for (int i = 0; i < m; i++) {
        for (int j = 0; j < n; j++) {
            // 对于每一个细胞统计其八个相邻位置里的活细胞数量
            int liveNeighbors = 0;
            for (int k = 0; k < 8; k++) {
                int nextRow = i + directions[k][0];
                int nextCol = j + directions[k][1];
                 if (nextRow >= 0 && nextRow < m && nextCol >= 0 && nextCol < n) {
                    if (abs(board[nextRow][nextCol]) == 1)liveNeighbors++;
                }
            }
            // 1. 如果活细胞周围八个位置的活细胞数少于两个，则该位置活细胞死亡；
            if (board[i][j] == 1 && (liveNeighbors < 2 || liveNeighbors > 3)) {
                board[i][j] = -1;
            }
            // 2. 如果活细胞周围八个位置有两个或三个活细胞，则该位置活细胞仍然存活；

            // 3. 如果活细胞周围八个位置有超过三个活细胞，则该位置活细胞死亡；

            // 4. 如果死细胞周围正好有三个活细胞，则该位置死细胞复活；
            if (board[i][j] == 0 && liveNeighbors == 3) {
                board[i][j] = 2;
            }
        }
    }

    // 遍历 board 得到一次更新后的状态
    for (int row = 0; row < m; row++) {
        for (int col = 0; col < n; col++) {
            if (board[row][col] > 0) {
                board[row][col] = 1;
            } else {
                board[row][col] = 0;
            }
        }
    }
}

// 方案一：使用辅助数组
// 时间复杂度：O(mn)
// 空间复杂度：O(mn)
void gameOfLife1(int** board, int boardSize, int* boardColSize) {
    int directions[8][2] = {
        {-1, 0}, {1, 0}, {0, -1}, {0, 1},
        {-1, -1}, {-1, 1}, {1, -1}, {1, 1}
    };
    int m = boardSize;
    int n = *boardColSize;
    // 创建复制数组 copyBoard
    int copyBoard[m][n];
    // 从原数组复制一份到 copyBoard 中
    for (int i = 0; i < m; i++) {
        for (int j = 0; j < n; j++) {
            copyBoard[i][j] = board[i][j];
        }
    }

    // 遍历每个细胞，并确定它最终的状态
    for (int i = 0; i < m; i++) {
        for (int j = 0; j < n; j++) {
            // 对于每一个细胞统计其八个相邻位置里的活细胞数量
            int liveNeighbors = 0;
            for (int k = 0; k < 8; k++) {
                int nextRow = i + directions[k][0];
                int nextCol = j + directions[k][1];
                 if (nextRow >= 0 && nextRow < m && nextCol >= 0 && nextCol < n && copyBoard[nextRow][nextCol] == 1) {
                    liveNeighbors++;
                }
            }
            // 1. 如果活细胞周围八个位置的活细胞数少于两个，则该位置活细胞死亡；
            if (copyBoard[i][j] == 1 && (liveNeighbors < 2 || liveNeighbors > 3)) {
                board[i][j] = 0;
            }
            // 2. 如果活细胞周围八个位置有两个或三个活细胞，则该位置活细胞仍然存活；

            // 3. 如果活细胞周围八个位置有超过三个活细胞，则该位置活细胞死亡；

            // 4. 如果死细胞周围正好有三个活细胞，则该位置死细胞复活；
            if (copyBoard[i][j] == 0 && liveNeighbors == 3) {
                board[i][j] = 1;
            }
        }
    }
}